Problems tagged with "asymptotic notation"

True.

Since \(\log n\) grows more slowly than \(n\), we have \(3n^2 \log n \leq 3n^2 \cdot n = 3n^3\) for all \(n \geq 1\), so \(f(n) = O(n^3)\). (In fact, \(f(n) = \Theta(n^2 \log n)\).)

\(\Omega(n)\), \(\Theta(n^2)\), \(O(n^2)\), \(\Omega(n^2)\), and \(O(n^3)\). Since \(f(n) = \Theta(n^2)\), it is \(O\) of anything that grows at least as fast as \(n^2\) and \(\Omega\) of anything that grows at most as fast as \(n^2\). It is not \(O(n)\) (and so not \(\Theta(n)\)), and it is not \(\Omega(n^3)\) (and so not \(\Theta(n^3)\)).

True.

The leading term of the numerator is \(n^3\) and the leading term of the denominator is \(n\), so \(f(n) = \Theta(n^2)\). Anything that is \(\Theta(n^2)\) is also \(O(n^4)\), since \(O\) only gives an upper bound.

True.

For every \(n\), \(3n \leq f(n) \leq 5n\), so \(f(n)\) is bounded above and below by constant multiples of \(n\). It doesn't matter that \(f\) jumps between two different constants.

True. This function is upper bounded by 3 and lower bounded by 1 for all \(n\), and is therefore \(\Theta(1)\).

True. We saw that this function is \(\Theta(1)\), but it is also correct to say that it is \(O(n^3)\), though this is not a tight upper bound.

True.

Asymptotic notation only describes how the time grows for large \(n\) and hides constants. For example, if A takes \(1000n^2\) steps and B takes \(2^n\) steps, then B is faster on every input of size \(n = 10\)(1024 steps vs. 100,000).

False. Algorithm A could have really large constants. For example, it could take 1,000,000 \(n^2\) seconds to run, while algorithm B takes \(.0001 n^3\) seconds to run. Algorithm B will still be better for \(n = 100\).

True.

Note that \(2^{3 + \log n} = 8 \cdot 2^{\log n} = 8n\), so the dominant term in the numerator is \(n^8\), while the dominant term in the denominator is \(20n^5\). Therefore \(f(n) = \Theta(n^3)\), which is \(O(n^4)\).

True.

Since \(2^{3 + \log n} = 8n\), the numerator is dominated by \(n^8\) and the denominator by \(20n^5\), so \(f(n) = \Theta(n^3)\). Anything that is \(\Theta(n^3)\) is also \(\Omega(n^2)\), since \(\Omega\) only gives a lower bound.

False.

Keeping only the dominant terms, the first factor is \(\Theta(n^3 / \sqrt n) = \Theta(n^{2.5})\) and the second is \(\Theta(n / n^3) = \Theta(1/n^2)\). Multiplying by \(n^2\) gives \(f(n) = \Theta(n^{2.5})\), which is not \(\Theta(n^2)\)(it is not \(O(n^2)\)).

\(f(n) = \Theta(\sqrt n \log n)\)

\(f(n) = \Theta(n^2)\)

\(\Theta(n^3)\)

False.

Remember that for \(f(n)\) to be \(\Theta(n)\), it has to be both upper- and lower-bounded by some positive constant times \(n\). This function is upper bounded by \(O(n)\), but it doesn't have a lower bound of \(\Omega(n)\). Therefore, it can't be \(\Theta(n)\).

In other words, there is no positive constant \(c\) and no positive number \(N\) such that \(f(n) > c n\) for all \(n > N\).

If you had to describe this function in asymptotic notation, you could say that \(f(n) = O(n)\)(and that would be a tight upper bound), but there is no lower bound, since the function keeps coming back down to zero.

False.

\(f(n)\) grows arbitrarily large, while \(\sin n + 1\) is bounded above by 2.

More formally, there is no constant \(c\) such that \(c (1 + \sin n)\) upper bounds \(f(n)\) for all large \(n\).

True.

Since \(\sin(n) + 1\) is always between 0 and 2, we have \(0 \leq f(n) \leq 2n\), so \(f(n) = O(n)\) and therefore also \(O(n^3)\). (The oscillation only prevents \(f\) from being \(\Omega(n)\); it doesn't affect the upper bound.)

False.

\(f(n)\)is upper bounded by \(O(n^2)\), but it doesn't have a lower bound of \(\Omega(n^2)\), which is necessary for it to be \(\Theta(n^2)\).

To see why, remember that for \(f(n)\) to be \(\Omega(n^2)\), there must be a positive constant \(c\) so that \(f(n)\) stays above \(c\cdot n^2\) for all \(n\) greater than some \(n_0\), meaning that it goes above \(c n^2\)and it stays above $c n^2$ forever, after some point.

Pick whatever positive \(c\) you'd like -- the function \(c\cdot n^2\) grows larger and larger as \(n\) increases, and eventually becomes larger than 1. But the function \(f(n)\) keeps dipping down to 1, meaning that it doesn't stay above \(c\cdot n^2\) for all \(n\) when \(n\) is large. Therefore, \(f(n)\) is not \(\Omega(n^2)\), and therefore also not \(\Theta(n^2)\).

\(\Theta(n)\). Using \(\frac{1}{\log_2 n} = \log_n 2\), we get \(n^{1/\log_2 n} = n^{\log_n 2} = 2\). So \(f(n) = 2n = \Theta(n)\).

\(\Theta(n^2)\). Inside the logarithm, the term \(3^{(n^2 - 2n)}\) dominates the others (which grow at most like \(n^2\)), so for large \(n\) the argument is between \(\frac{1}{2} \cdot 3^{(n^2 - 2n)}\) and \(2 \cdot 3^{(n^2 - 2n)}\). Taking \(\log_2\), \(f(n)\) is within a constant of \(12 (n^2 - 2n) \log_2 3\), which is \(\Theta(n^2)\).

True.

The upper bound: both \(f_1\) and \(f_2\) are \(O(n^2)\), so their sum is \(O(n^2)\). The lower bound: \(f_1\) is nonnegative (for large \(n\)), so \(f_1(n) + f_2(n) \geq f_2(n)\), which is \(\Omega(n^2)\).

\(\Theta(n^3)\)

\(O(n^5)\) and \(\Omega(n^4)\)

True.

Both functions are nonnegative (for large \(n\)), so \(f_1(n) + f_2(n) \geq f_1(n)\), and \(f_1(n) = \Omega(n)\). Adding a nonnegative function can only make the sum bigger, so it can't hurt a lower bound.

\(O(n)\)

True.

Both functions are nonnegative (for large \(n\)), so \(f_1(n) + f_2(n) \geq f_1(n)\), and \(f_1(n) = \Omega(n^2)\). The weaker lower bound on \(f_2\) doesn't matter, since adding \(f_2\) can only make the sum larger.

\(O(n^2)\)

False. Counterexample: \(f = n^{6.5}\). This is neither \(\Theta(n^5)\) or \(\Theta(n^6)\) or \(\Theta(n^7)\); it is \(\Theta(n^{6.5})\).

False.

We know nothing about how large \(f_2\) can be, so it can dominate the sum. For example, take \(f_1(n) = g_1(n) = g_2(n) = 1\) and \(f_2(n) = n^2\). Then \(f_2 = \Omega(1)\), but \(f_1(n) + f_2(n) = 1 + n^2\) is not \(O(1)\).

False. Take \(f(n) = n^3\) and \(g(n) = n^3\). We can see from definition that \(f(n) = \Omega(n^3)\) and \(g(n) = \Omega(n)\). However,

The key takeaway for this question is, since \(g\) is on the denominator, we can make it grow arbitrarily fast, so that \(f/g\) do not meet the requirements that we want.

False.

\(f_1\) could be as large as \(n^2\). For example, if \(f_1(n) = f_2(n) = n^2\), then \(g(n) = 1\), which is not \(\Omega(n)\). (We only know \(g(n) = \Omega(1)\) and \(g(n) = O(n)\).)

False. Try breaking it with a counterexample. What if \(f_1 = n^3\), \(f_2 = n^2\), \(g_1 = n^3\) and \(g_2 = n^3\). All of the conditions are satisfied, but \(f_1/f_2 = n\), while \(g_1/g_2 = 1\), so \(f_1 / f_2\) is not \(\Theta(g_1/g_2)\).

True.

For large \(n\), \(f_1(n) \leq c_1 g_1(n)\) and \(f_2(n) \leq c_2 g_2(n)\). The minimum of \(f_1\) and \(f_2\) is at most each of them, so with \(c = \max\{c_1, c_2\}\) we get \(\min\{f_1(n), f_2(n)\}\leq c \, g_1(n)\) and \(\leq c \, g_2(n)\), i.e., \(f(n) \leq c \min\{g_1(n), g_2(n)\}\).

True.

For large \(n\), \(f_1(n) \geq c_1 g_1(n)\) and \(f_2(n) \geq c_2 g_2(n)\). Letting \(c = \min\{c_1, c_2\}\), whichever of \(f_1(n)\) or \(f_2(n)\) is smaller is still at least \(c\) times the corresponding \(g\), which is at least \(c \min\{g_1(n), g_2(n)\}\). So \(f(n) \geq c \, g(n)\).

True.

For large \(n\), \(f_1(n) \geq c_1 g_1(n)\) and \(f_2(n) \geq c_2 g_2(n)\). Letting \(c = \min\{c_1, c_2\}\), \(\max\{f_1(n), f_2(n)\}\) is at least both \(c\, g_1(n)\) and \(c\, g_2(n)\), so it is at least \(c \max\{g_1(n), g_2(n)\}\).